package com.example.demo.leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 链接：<a href="https://leetcode.cn/problems/beautiful-towers-i/description/?envType=daily-question&envId=2024-01-24">https://leetcode.cn/problems/beautiful-towers-i/description/?envType=daily-question&envId=2024-01-24</a><br>
 * <p>
 * 给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。<br>
 * <p>
 * 你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ，高度为 heights[i] 。<br>
 * <p>
 * <p>
 * 如果以下条件满足，我们称这些塔是 美丽 的：<br>
 * <p>
 * 1 <= heights[i] <= maxHeights[i]<br>
 * heights 是一个 山脉 数组。<br>
 * <p>
 * <p>
 * 如果存在下标 i 满足以下条件，那么我们称数组 heights 是一个 山脉 数组：<br>
 * <p>
 * 对于所有 0 < j <= i ，都有 heights[j - 1] <= heights[j]<br>
 * 对于所有 i <= k < n - 1 ，都有 heights[k + 1] <= heights[k]<br>
 * <p>
 * <p>
 * 请你返回满足 美丽塔 要求的方案中，高度和的最大值 。<br>
 *
 * @author WangYX
 * @version 1.0.0
 * @date 2024/01/24 17:23
 */
public class _2865_美丽塔Ⅰ {

    public static void main(String[] args) {
        List<Integer> maxHeights = new ArrayList<>();
        maxHeights.add(5);
        maxHeights.add(3);
        maxHeights.add(4);
        maxHeights.add(1);
        maxHeights.add(1);

        List<Integer> maxHeights1 = new ArrayList<>();
        maxHeights1.add(6);
        maxHeights1.add(5);
        maxHeights1.add(3);
        maxHeights1.add(9);
        maxHeights1.add(2);
        maxHeights1.add(7);

        List<Integer> maxHeights2 = new ArrayList<>();
        maxHeights2.add(3);
        maxHeights2.add(6);
        maxHeights2.add(3);
        maxHeights2.add(5);
        maxHeights2.add(5);
        maxHeights2.add(1);
        maxHeights2.add(2);
        maxHeights2.add(5);
        maxHeights2.add(5);
        maxHeights2.add(6);

        List<Integer> maxHeights3 = new ArrayList<>();
        maxHeights3.add(5);
        maxHeights3.add(2);
        maxHeights3.add(4);
        maxHeights3.add(4);

        long l = new Solution().maximumSumOfHeights1(maxHeights2);
        System.out.println(l);
    }

    public static class Solution {

        /**
         * 方法1：暴力求解。<br>
         * <p>
         * 我们依次枚举以 maxHeights[i] 为山顶的山状数组元素之和即可求出最大的高度和。根据山状数组的定义，我们采用两层循环，外层循环依次枚举 maxHeights[i] 为山顶，在内层循环中分别求出索引 i 的左侧元素与右侧元素，即可求出所有元素之和，返回元素之和的最大值即可。
         * <p>
         * <p>
         * 时间复杂都为O(n^2),其中 n 表示给定数组的长度。枚举山状数组的最大值需要的时间为 O(n)，给定最大值求数组元素的和需要的时间为 O(n)，因此总的时间为 O(n^2)。 <br>
         * <p>
         * 空间复杂都为O(1)
         *
         * @param maxHeights
         * @return
         */
        public long maximumSumOfHeights(List<Integer> maxHeights) {
            long total = 0;
            for (int i = 0; i < maxHeights.size(); i++) {
                int max = maxHeights.get(i);
                long sum = 0;
                int rightMin = max;
                for (int j = i + 1; j < maxHeights.size(); j++) {
                    rightMin = Math.min(rightMin, maxHeights.get(j));
                    sum += rightMin;
                }
                int leftMin = max;
                for (int j = i - 1; j >= 0; j--) {
                    leftMin = Math.min(leftMin, maxHeights.get(j));
                    sum += leftMin;
                }
                total = Math.max(total, sum + max);
            }
            return total;
        }

        public long maximumSumOfHeights1(List<Integer> maxHeights) {
            int n = maxHeights.size();
            long res = 0;
            long[] prefix = new long[n];
            long[] suffix = new long[n];
            Deque<Integer> stack1 = new ArrayDeque<Integer>();
            Deque<Integer> stack2 = new ArrayDeque<Integer>();

            for (int i = 0; i < n; i++) {
                while (!stack1.isEmpty() && maxHeights.get(i) < maxHeights.get(stack1.peek())) {
                    stack1.pop();
                }
                if (stack1.isEmpty()) {
                    prefix[i] = (long) (i + 1) * maxHeights.get(i);
                } else {
                    prefix[i] = prefix[stack1.peek()] + (long) (i - stack1.peek()) * maxHeights.get(i);
                }
                stack1.push(i);
            }
            for (int i = n - 1; i >= 0; i--) {
                while (!stack2.isEmpty() && maxHeights.get(i) < maxHeights.get(stack2.peek())) {
                    stack2.pop();
                }
                if (stack2.isEmpty()) {
                    suffix[i] = (long) (n - i) * maxHeights.get(i);
                } else {
                    suffix[i] = suffix[stack2.peek()] + (long) (stack2.peek() - i) * maxHeights.get(i);
                }
                stack2.push(i);
                res = Math.max(res, prefix[i] + suffix[i] - maxHeights.get(i));
            }
            return res;
        }
    }
}
